package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/24 20:17
 * @description <p>回文子字符串的个数 </p>
 */

import java.util.Objects;

/**
 * 题目：给定一个字符串，请问该字符串中有多少个回文连续子字符串？
 * 例如，字符串"abc"有 3 个回文子字符串，分别为"a"、"b"和"c"；而字符串
 * "aaa"有 6 个回文子字符串，分别为"a"、"a"、"a"、"aa"、"aa"和"aaa"。
 */
public class toOffer4_3_20 {
    public static void main(String[] args) {
        String s = "aaa";
        System.out.println(countSubstrings(s));
    }

    /**
     * @param s
     * @return
     */
    public static int countSubstrings(String s) {
        //判空
        if (Objects.isNull(s) || s.length() == 0) {
            return 1;
        }

        int result = 0;
        //扩散计算回文数量。
        for (int i = 0; i < s.length(); i++) {
            //回文分两种情况：偶数和奇数
            //奇数
            result += countResult(s, i, i);
            //偶数
            result += countResult(s, i, i + 1);
        }

        return result;
    }

    /**
     * 计算回文数量
     * @param s
     * @param left
     * @param right
     * @return
     */
    private static int countResult(String s, int left, int right) {
        int result = 0;
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
            result++;
        }
        return result;
    }
}
